package week_02;

import java.util.Arrays;

public class MergeKSortList_23_2 {

    public static ListNode[] lists;

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null) return null;
        this.lists = lists;
        return mergeKLists(0, lists.length - 1);
    }

    public ListNode mergeKLists(int l, int r) {
        if (l == r) {
            return lists[0];
        } else if (l + 1 == r) {
            return merge(lists[l], lists[r]);
        } else {
            int mid = l + (r - l) / 2;
            ListNode node1 = mergeKLists(l, mid);
            ListNode node2 = mergeKLists(mid + 1, r);
            return merge(node1, node2);
        }
    }

    private ListNode merge(ListNode node1, ListNode node2) {
        ListNode root = new ListNode();
        ListNode cur = root;

        while (node1 != null && node2 != null) {
            if (node1.val <= node2.val) {
                cur.next = node1;
                node1 = node1.next;
            } else {
                cur.next = node2;
                node2 = node2.next;
            }
            cur = cur.next;
        }
        if (node1 != null) {
            cur.next = node1;
        }

        if (node2 != null) {
            cur.next = node2;
        }
        return root.next;
    }

    private void printList(ListNode node) {
        while (node != null) {
            System.out.printf(node.val + " ");
            node = node.next;
        }
        System.out.println();
    }
}

//    public static void main(String[] args) {
//        int N = 10;
//        int[] arr = new int[N];
//        for (int i = 0; i < N; i++) {
//            arr[i] = i;
//        }
//
//        int[] arr1 = Arrays.copyOfRange(arr, 0, N / 2);
//        int[] arr2 = Arrays.copyOfRange(arr, N / 2, N);
//    }